/*
 * 数据处理算法模板库 - 数据分析和处理工具
 * 使用场景: 数据统计、数组处理、算法优化、数据变换
 * 包含: 统计分析、数组操作、排序算法、数据变换、常用算法
 * 特点: 提供高效的数据处理和分析工具
 */

#pragma once
#include "basic_template.hpp"
#include <functional>
#include <numeric>

// 数据统计分析工具
namespace DataUtils
{
// 数组统计信息结构体
template <typename T>
struct Statistics {
    T min_val, max_val, sum;
    double mean, median;
    int count;

    // 构造函数：计算数组的完整统计信息
    // data: 输入数据数组
    Statistics(const vector<T> &data)
    {
        if (data.empty()) {
            min_val = max_val = sum = T{};
            mean = median = 0.0;
            count = 0;
            return;
        }

        count = data.size();
        min_val = *min_element(data.begin(), data.end());
        max_val = *max_element(data.begin(), data.end());
        sum = accumulate(data.begin(), data.end(), T{});
        mean = (double)sum / count;

        vector<T> sorted_data = data;
        sort(sorted_data.begin(), sorted_data.end());
        if (count % 2 == 0) {
            median = ((double)sorted_data[count / 2 - 1] + sorted_data[count / 2]) / 2.0;
        } else {
            median = sorted_data[count / 2];
        }
    }
};

// 快速排序（带自定义比较器）
// arr: 要排序的数组
// comp: 自定义比较函数
template <typename T, typename Compare>
void quick_sort(vector<T> &arr, Compare comp)
{
    sort(arr.begin(), arr.end(), comp);
}

// 数组去重（保持原有顺序）
// arr: 输入数组
// 返回值: 去重后的数组
template <typename T>
vector<T> unique_preserve_order(const vector<T> &arr)
{
    vector<T> result;
    unordered_set<T> seen;
    for (const T &item : arr) {
        if (seen.find(item) == seen.end()) {
            seen.insert(item);
            result.push_back(item);
        }
    }
    return result;
}

// 数组分组：根据键函数将数组元素分组
// arr: 输入数组
// key_func: 键提取函数
// 返回值: 分组后的映射表
template <typename T, typename KeyFunc>
map<typename result_of<KeyFunc(T)>::type, vector<T>> group_by(const vector<T> &arr, KeyFunc key_func)
{
    map<typename result_of<KeyFunc(T)>::type, vector<T>> groups;
    for (const T &item : arr) {
        groups[key_func(item)].push_back(item);
    }
    return groups;
}

// 数组过滤：根据谓词函数过滤元素
// arr: 输入数组
// pred: 谓词函数，返回true的元素被保留
// 返回值: 过滤后的数组
template <typename T, typename Predicate>
vector<T> filter(const vector<T> &arr, Predicate pred)
{
    vector<T> result;
    for (const T &item : arr) {
        if (pred(item)) {
            result.push_back(item);
        }
    }
    return result;
}

// 数组映射变换：将每个元素通过函数变换为新类型
// arr: 输入数组
// func: 变换函数
// 返回值: 变换后的数组
template <typename T, typename U, typename Func>
vector<U> map_transform(const vector<T> &arr, Func func)
{
    vector<U> result;
    result.reserve(arr.size());
    for (const T &item : arr) {
        result.push_back(func(item));
    }
    return result;
}

// 数组累积：使用二元函数累积数组元素
// arr: 输入数组
// init: 初始值
// func: 累积函数
// 返回值: 累积结果
template <typename T, typename Func>
T reduce(const vector<T> &arr, T init, Func func)
{
    T result = init;
    for (const T &item : arr) {
        result = func(result, item);
    }
    return result;
}

// 生成数字序列
// start: 起始值
// end: 结束值（不包含）
// step: 步长
// 返回值: 数字序列
vector<int> range(int start, int end, int step = 1)
{
    vector<int> result;
    if (step > 0) {
        for (int i = start; i < end; i += step) {
            result.push_back(i);
        }
    } else if (step < 0) {
        for (int i = start; i > end; i += step) {
            result.push_back(i);
        }
    }
    return result;
}

// 数组切片：提取数组的子序列
// arr: 输入数组
// start: 起始索引
// end: 结束索引（不包含），-1表示到末尾
// 返回值: 切片后的数组
template <typename T>
vector<T> slice(const vector<T> &arr, int start, int end = -1)
{
    if (end == -1)
        end = arr.size();
    if (start < 0)
        start = 0;
    if (end > (int)arr.size())
        end = arr.size();
    if (start >= end)
        return {};

    return vector<T>(arr.begin() + start, arr.begin() + end);
}

// 数组左旋转
// arr: 输入数组
// k: 旋转位数
// 返回值: 旋转后的数组
template <typename T>
vector<T> rotate_left(const vector<T> &arr, int k)
{
    if (arr.empty())
        return arr;
    k = k % arr.size();
    vector<T> result = arr;
    rotate(result.begin(), result.begin() + k, result.end());
    return result;
}

// 数组右旋转
// arr: 输入数组
// k: 旋转位数
// 返回值: 旋转后的数组
template <typename T>
vector<T> rotate_right(const vector<T> &arr, int k)
{
    if (arr.empty())
        return arr;
    k = k % arr.size();
    return rotate_left(arr, arr.size() - k);
}

// 计算数组的方差
// data: 输入数据
// 返回值: 方差值
template <typename T>
double variance(const vector<T> &data)
{
    if (data.empty())
        return 0.0;

    double mean = (double)accumulate(data.begin(), data.end(), T{}) / data.size();
    double sum_sq_diff = 0.0;

    for (const T &val : data) {
        double diff = val - mean;
        sum_sq_diff += diff * diff;
    }

    return sum_sq_diff / data.size();
}

// 计算数组的标准差
// data: 输入数据
// 返回值: 标准差值
template <typename T>
double standard_deviation(const vector<T> &data)
{
    return sqrt(variance(data));
}

// 查找数组中的众数（出现次数最多的元素）
// data: 输入数据
// 返回值: 众数和其出现次数的pair
template <typename T>
pair<T, int> mode(const vector<T> &data)
{
    if (data.empty())
        return {T{}, 0};

    unordered_map<T, int> freq;
    for (const T &val : data) {
        freq[val]++;
    }

    T mode_val = data[0];
    int max_freq = 0;

    for (const auto &p : freq) {
        if (p.second > max_freq) {
            max_freq = p.second;
            mode_val = p.first;
        }
    }

    return {mode_val, max_freq};
}

// 计算百分位数
// data: 输入数据
// percentile: 百分位数（0-100）
// 返回值: 对应的百分位数值
template <typename T>
double percentile(vector<T> data, double percentile)
{
    if (data.empty())
        return 0.0;

    sort(data.begin(), data.end());
    double index = (percentile / 100.0) * (data.size() - 1);

    if (index == floor(index)) {
        return data[(int)index];
    } else {
        int lower = (int)floor(index);
        int upper = (int)ceil(index);
        double weight = index - lower;
        return data[lower] * (1 - weight) + data[upper] * weight;
    }
}

// 数组的滑动窗口操作
// data: 输入数据
// window_size: 窗口大小
// func: 窗口内的聚合函数
// 返回值: 每个窗口的聚合结果
template <typename T, typename Func>
vector<T> sliding_window(const vector<T> &data, int window_size, Func func)
{
    vector<T> result;
    if (data.size() < window_size)
        return result;

    for (int i = 0; i <= (int)data.size() - window_size; i++) {
        vector<T> window(data.begin() + i, data.begin() + i + window_size);
        result.push_back(func(window));
    }

    return result;
}
} // namespace DataUtils

// 常用算法模板集合
namespace CommonAlgorithms
{
// 二分查找（返回位置）
// arr: 已排序的数组
// target: 要查找的目标值
// 返回值: 目标值的索引，未找到返回-1
template <typename T>
int binary_search_pos(const vector<T> &arr, const T &target)
{
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到
}

// 快速幂算法
// base: 底数
// exp: 指数
// mod: 模数（0表示不取模）
// 返回值: base^exp (mod mod)
template <typename T>
T fast_power(T base, T exp, T mod = 0)
{
    T result = 1;
    if (mod > 0)
        base = base % mod;

    while (exp > 0) {
        if (exp & 1) {
            result = (mod > 0) ? (result * base) % mod : result * base;
        }
        exp >>= 1;
        base = (mod > 0) ? (base * base) % mod : base * base;
    }
    return result;
}

// 最大公约数（欧几里得算法）
// a, b: 两个整数
// 返回值: a和b的最大公约数
template <typename T>
T gcd(T a, T b)
{
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// 最小公倍数
// a, b: 两个整数
// 返回值: a和b的最小公倍数
template <typename T>
T lcm(T a, T b)
{
    return a / gcd(a, b) * b;
}

// 扩展欧几里得算法
// a, b: 两个整数
// x, y: 引用参数，返回满足ax + by = gcd(a,b)的x和y
// 返回值: gcd(a, b)
template <typename T>
T extended_gcd(T a, T b, T &x, T &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    T x1, y1;
    T gcd_val = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd_val;
}

// 判断质数
// n: 要判断的数
// 返回值: 是质数返回true，否则返回false
bool is_prime(long long n)
{
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

// 生成质数（埃拉托斯特尼筛法）
// n: 上限值
// 返回值: 布尔数组，is_prime[i]表示i是否为质数
vector<bool> sieve_of_eratosthenes(int n)
{
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// 计算阶乘
// n: 非负整数
// 返回值: n的阶乘
long long factorial(int n)
{
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 计算组合数C(n, r)
// n: 总数
// r: 选择数
// 返回值: C(n, r)的值
long long combination(int n, int r)
{
    if (r > n || r < 0)
        return 0;
    if (r == 0 || r == n)
        return 1;

    // 优化：选择较小的r
    if (r > n - r)
        r = n - r;

    long long result = 1;
    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

// 计算排列数P(n, r)
// n: 总数
// r: 选择数
// 返回值: P(n, r)的值
long long permutation(int n, int r)
{
    if (r > n || r < 0)
        return 0;

    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= (n - i);
    }
    return result;
}

// 矩阵快速幂
// matrix: 方阵
// n: 幂次
// mod: 模数
// 返回值: matrix^n (mod mod)
vector<vector<long long>> matrix_power(vector<vector<long long>> matrix, long long n, long long mod)
{
    int size = matrix.size();
    vector<vector<long long>> result(size, vector<long long>(size, 0));

    // 初始化为单位矩阵
    for (int i = 0; i < size; i++) {
        result[i][i] = 1;
    }

    while (n > 0) {
        if (n & 1) {
            // 矩阵乘法
            vector<vector<long long>> temp(size, vector<long long>(size, 0));
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    for (int k = 0; k < size; k++) {
                        temp[i][j] = (temp[i][j] + result[i][k] * matrix[k][j]) % mod;
                    }
                }
            }
            result = temp;
        }

        // matrix = matrix * matrix
        vector<vector<long long>> temp(size, vector<long long>(size, 0));
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    temp[i][j] = (temp[i][j] + matrix[i][k] * matrix[k][j]) % mod;
                }
            }
        }
        matrix = temp;
        n >>= 1;
    }

    return result;
}

// 约瑟夫问题
// n: 总人数
// k: 每次数到第k个人
// 返回值: 最后剩下的人的位置（0-based）
int josephus(int n, int k)
{
    int result = 0;
    for (int i = 2; i <= n; i++) {
        result = (result + k) % i;
    }
    return result;
}

// 计算逆元（费马小定理）
// a: 要求逆元的数
// mod: 模数（必须是质数）
// 返回值: a在模mod下的逆元
long long mod_inverse(long long a, long long mod)
{
    return fast_power(a, mod - 2, mod);
}
} // namespace CommonAlgorithms
